home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / ICON_8 / BENCH_FO / RSG.ICN < prev    next >
Text File  |  1990-04-06  |  11KB  |  386 lines
  1. ############################################################################
  2. #
  3. #    Name:    rsg.icn
  4. #
  5. #    Title:    Generate randomly selected sentences from a grammar
  6. #
  7. #    Author:    Ralph E. Griswold
  8. #
  9. #    Date:    June 10, 1988
  10. #
  11. ############################################################################
  12. #  
  13. #     This program generates randomly selected strings (``sen-
  14. #  tences'') from a grammar specified by the user.  Grammars are
  15. #  basically context-free and resemble BNF in form, although there
  16. #  are a number of extensions.
  17. #  
  18. #     The program works interactively, allowing the user to build,
  19. #  test, modify, and save grammars. Input to rsg consists of various
  20. #  kinds of specifications, which can be intermixed:
  21. #  
  22. #     Productions define nonterminal symbols in a syntax similar to
  23. #  the rewriting rules of BNF with various alternatives consisting
  24. #  of the concatenation of nonterminal and terminal symbols.  Gen-
  25. #  eration specifications cause the generation of a specified number
  26. #  of sentences from the language defined by a given nonterminal
  27. #  symbol.  Grammar output specifications cause the definition of a
  28. #  specified nonterminal or the entire current grammar to be written
  29. #  to a given file.  Source specifications cause subsequent input to
  30. #  be read from a specified file.
  31. #  
  32. #     In addition, any line beginning with # is considered to be a
  33. #  comment, while any line beginning with = causes the rest of that
  34. #  line to be used subsequently as a prompt to the user whenever rsg
  35. #  is ready for input (there normally is no prompt). A line consist-
  36. #  ing of a single = stops prompting.
  37. #  
  38. #  Productions: Examples of productions are:
  39. #  
  40. #          <expr>::=<term>|<term>+<expr>
  41. #          <term>::=<elem>|<elem>*<term>
  42. #          <elem>::=x|y|z|(<expr>)
  43. #  
  44. #  Productions may occur in any order. The definition for a nonter-
  45. #  minal symbol can be changed by specifying a new production for
  46. #  it.
  47. #  
  48. #     There are a number of special devices to facilitate the defin-
  49. #  ition of grammars, including eight predefined, built-in nontermi-
  50. #  nal symbols:
  51. #     symbol   definition
  52. #     <lb>     <
  53. #     <rb>     >
  54. #     <vb>     |
  55. #     <nl>     newline
  56. #     <>       empty string
  57. #     <&lcase> any single lowercase letter
  58. #     <&ucase> any single uppercase letter
  59. #     <&digit> any single digit
  60. #  
  61. #  In addition, if the string between a < and a > begins and ends
  62. #  with a single quotation mark, it stands for any single character
  63. #  between the quotation marks. For example,
  64. #  
  65. #          <'xyz'>
  66. #  
  67. #  is equivalent to
  68. #  
  69. #          x|y|z
  70. #  
  71. #  Generation Specifications: A generation specification consists of
  72. #  a nonterminal symbol followed by a nonnegative integer. An exam-
  73. #  ple is
  74. #  
  75. #          <expr>10
  76. #  
  77. #  which specifies the generation of 10 <expr>s. If the integer is
  78. #  omitted, it is assumed to be 1. Generated sentences are written
  79. #  to standard output.
  80. #  
  81. #  Grammar Output Specifications: A grammar output specification
  82. #  consists of a nonterminal symbol, followed by ->, followed by a
  83. #  file name. Such a specification causes the current definition of
  84. #  the nonterminal symbol to be written to the given file. If the
  85. #  file is omitted, standard output is assumed. If the nonterminal
  86. #  symbol is omitted, the entire grammar is written out. Thus,
  87. #  
  88. #          ->
  89. #  
  90. #  causes the entire grammar to be written to standard output.
  91. #  
  92. #  Source Specifications: A source specification consists of @ fol-
  93. #  lowed by a file name.  Subsequent input is read from that file.
  94. #  When an end of file is encountered, input reverts to the previous
  95. #  file. Input files can be nested.
  96. #  
  97. #  Options: The following options are available:
  98. #  
  99. #       -s n Set the seed for random generation to n.  The default
  100. #            seed is 0.
  101. #  
  102. #       -l n Terminate generation if the number of symbols remaining
  103. #            to be processed exceeds n. The default is limit is 1000.
  104. #  
  105. #       -t   Trace the generation of sentences. Trace output goes to
  106. #            standard error output.
  107. #  
  108. #  Diagnostics: Syntactically erroneous input lines are noted but
  109. #  are otherwise ignored.  Specifications for a file that cannot be
  110. #  opened are noted and treated as erroneous.
  111. #  
  112. #     If an undefined nonterminal symbol is encountered during gen-
  113. #  eration, an error message that identifies the undefined symbol is
  114. #  produced, followed by the partial sentence generated to that
  115. #  point. Exceeding the limit of symbols remaining to be generated
  116. #  as specified by the -l option is handled similarly.
  117. #  
  118. #  Caveats: Generation may fail to terminate because of a loop in
  119. #  the rewriting rules or, more seriously, because of the progres-
  120. #  sive accumulation of nonterminal symbols. The latter problem can
  121. #  be identified by using the -t option and controlled by using the
  122. #  -l option. The problem often can be circumvented by duplicating
  123. #  alternatives that lead to fewer rather than more nonterminal sym-
  124. #  bols. For example, changing
  125. #  
  126. #          <term>::=<elem>|<elem>*<term>
  127. #  
  128. #  to
  129. #  
  130. #          <term>::=<elem>|<elem>|<elem>*<term>
  131. #  
  132. #  increases the probability of selecting <elem> from 1/2 to 2/3.
  133. #  
  134. #     There are many possible extensions to the program. One of the
  135. #  most useful would be a way to specify the probability of select-
  136. #  ing an alternative.
  137. #  
  138. ############################################################################
  139. #
  140. #  Links: options, post
  141. #
  142. ############################################################################
  143.  
  144. link options, post
  145.  
  146. global defs, ifile, in, limit, prompt, tswitch
  147.  
  148. record nonterm(name)
  149. record charset(chars)
  150.  
  151. procedure main(args)
  152.    local line, plist, s, opts
  153.  
  154.    Init__()
  155.  
  156.                     # procedures to try on input lines
  157.    plist := [define,generate,grammar,source,comment,prompter,error]
  158.    defs := table()            # table of definitions
  159.    defs["lb"] := [["<"]]        # built-in definitions
  160.    defs["rb"] := [[">"]]
  161.    defs["vb"] := [["|"]]
  162.    defs["nl"] := [["\n"]]
  163.    defs[""] := [[""]]
  164.    defs["&lcase"] := [[charset(&lcase)]]
  165.    defs["&ucase"] := [[charset(&ucase)]]
  166.    defs["&digit"] := [[charset(&digits)]]
  167.  
  168.    opts := options(args,"tl+s+")
  169.    limit := \opts["l"] | 1000
  170.    tswitch := \opts["t"]
  171.    &random := \opts["s"]
  172.  
  173.    ifile := [&input]            # stack of input files
  174.    prompt := ""
  175.    while in := pop(ifile) do {        # process all files
  176.       repeat {
  177.          if *prompt ~= 0 then writes(prompt)
  178.          line := read(in) | break
  179.          while line[-1] == "\\" do line := line[1:-1] || read(in) | break
  180.          (!plist)(line)
  181.          }
  182.       close(in)
  183.       }
  184.  
  185.    Term__()
  186.  
  187. end
  188.  
  189. #  process alternatives
  190. #
  191. procedure alts(defn)
  192.    local alist
  193.    alist := []
  194.    defn ? while put(alist,syms(tab(upto('|') | 0))) do move(1) | break
  195.    return alist
  196. end
  197.  
  198. #  look for comment
  199. #
  200. procedure comment(line)
  201.    if line[1] == "#" then return
  202. end
  203.  
  204. #  look for definition
  205. #
  206. procedure define(line)
  207.    return line ?
  208.       defs[(="<",tab(find(">::=")))] := (move(4),alts(tab(0)))
  209. end
  210.  
  211. #  define nonterminal
  212. #
  213. procedure defnon(sym)
  214.    local chars, name
  215.    if sym ? {
  216.       ="'" &
  217.       chars := cset(tab(-1)) &
  218.       ="'"
  219.       }
  220.    then return charset(chars)
  221.    else return nonterm(sym)
  222. end
  223.  
  224. #  note erroneous input line
  225. #
  226. procedure error(line)
  227.    write("*** erroneous line:  ",line)
  228.    return
  229. end
  230.  
  231. #  generate sentences
  232. #
  233. procedure gener(goal)
  234.    local pending, symbol
  235.    pending := [nonterm(goal)]
  236.    while symbol := get(pending) do {
  237.       if \tswitch then
  238.          write(&errout,symimage(symbol),listimage(pending))
  239.       case type(symbol) of {
  240.          "string":   writes(symbol)
  241.          "charset":  writes(?symbol.chars)
  242.          "nonterm":  {
  243.             pending := ?\defs[symbol.name] ||| pending | {
  244.                write(&errout,"*** undefined nonterminal:  <",symbol.name,">")
  245.                break 
  246.                }
  247.             if *pending > \limit then {
  248.                write(&errout,"*** excessive symbols remaining")
  249.                break 
  250.                }
  251.             }
  252.          }
  253.       }
  254.    write()
  255. end
  256.  
  257. #  look for generation specification
  258. #
  259. procedure generate(line)
  260.    local goal, count
  261.    if line ? {
  262.       ="<" &
  263.       goal := tab(upto('>')) \ 1 &
  264.       move(1) &
  265.       count := (pos(0) & 1) | integer(tab(0))
  266.       }
  267.    then {
  268.       every 1 to count do
  269.          gener(goal)
  270.       return
  271.       }
  272.    else fail
  273. end
  274.  
  275. #  get right hand side of production
  276. #
  277. procedure getrhs(a)
  278.    local rhs
  279.    rhs := ""
  280.    every rhs ||:= listimage(!a) || "|"
  281.    return rhs[1:-1]
  282. end
  283.  
  284. #  look for request to write out grammar
  285. #
  286. procedure grammar(line)
  287.    local file, out, name
  288.    if line ? {
  289.       name := tab(find("->")) &
  290.       move(2) &
  291.       file := tab(0) &
  292.       out := if *file = 0 then &output else {
  293.          open(file,"w") | {
  294.             write(&errout,"*** cannot open ",file)
  295.             fail
  296.             }
  297.          }
  298.       }
  299.    then {
  300.       (*name = 0) | (name[1] == "<" & name[-1] == ">") | fail
  301.       pwrite(name,out)
  302.       if *file ~= 0 then close(out)
  303.       return
  304.       }
  305.    else fail
  306. end
  307.  
  308. #  produce image of list of grammar symbols
  309. #
  310. procedure listimage(a)
  311.    local s, x
  312.    s := ""
  313.    every x := !a do
  314.       s ||:= symimage(x)
  315.    return s
  316. end
  317.  
  318. #  look for new prompt symbol
  319. #
  320. procedure prompter(line)
  321.    if line[1] == "=" then {
  322.       prompt := line[2:0]
  323.       return
  324.       }
  325. end
  326.  
  327. #  write out grammar
  328. #
  329. procedure pwrite(name,ofile)
  330.    local nt, a
  331.    static builtin
  332.    initial builtin := ["lb","rb","vb","nl","","&lcase","&ucase","&digit"]
  333.    if *name = 0 then {
  334.       a := sort(defs,3)
  335.       while nt := get(a) do {
  336.          if nt == !builtin then {
  337.             get(a)
  338.             next
  339.             }
  340.          write(ofile,"<",nt,">::=",getrhs(get(a)))
  341.          }
  342.       }
  343.    else write(ofile,name,"::=",getrhs(\defs[name[2:-1]])) |
  344.       write("*** undefined nonterminal:  ",name)
  345. end
  346.  
  347. #  look for file with input
  348. #
  349. procedure source(line)
  350.    local file, new
  351.  
  352.    return line ? {
  353.       if ="@" then {
  354.          new := open(file := tab(0)) | {
  355.             write(&errout,"*** cannot open ",file)
  356.             fail
  357.             }
  358.          push(ifile,in) &
  359.          in := new
  360.          return
  361.          }
  362.       }
  363. end
  364.  
  365. #  produce string image of grammar symbol
  366. #
  367. procedure symimage(x)
  368.    return case type(x) of {
  369.       "string":   x
  370.       "nonterm":  "<" || x.name || ">"
  371.       "charset":  "<'" || x.chars || "'>"
  372.       }
  373. end
  374.  
  375. #  process the symbols in an alternative
  376. #
  377. procedure syms(alt)
  378.    local slist
  379.    static nonbrack
  380.    initial nonbrack := ~'<'
  381.    slist := []
  382.    alt ? while put(slist,tab(many(nonbrack)) |
  383.       defnon(2(="<",tab(upto('>')),move(1))))
  384.    return slist
  385. end
  386.